/*
 * FileName: breadthfirstsearch.cc
 * Author: 李波(Edwin Lee)
 * Date: 2024-07-21 10:54:36
 * Version: 1.0
 * Description: 最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜索法来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。
 		算法：使用队列queue接收遍历的节点，使用vector接收路径节点
BUG:输出路径折角位置没有显示*,待修改
 */
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

class Maze
{
public:
	Maze()
		:row_(0)
		,col_(0)
		,pmaze_(nullptr)
		,findPath_(false)
	{}
/*
	Maze(int row, int col)
		:row_(row)
		,col_(col)
		,pmaze_(nullptr)
	{
		initMaze(row,col);
	}
*/
	void initMaze(int row, int col)
	{
		if(nullptr != pmaze_)
		{
			for(int i=0; i < row_; ++i)
			{
				delete []pmaze_[i];
			}
			delete []pmaze_;
		}

		row_ = row;
		col_ = col;
		srand(time(nullptr));
		vec_.resize(row*col);
		pmaze_ = new Node*[row];
		for(int i = 0; i < row; ++i)
		{
			pmaze_[i] = new Node[col];
			for(int j = 0; j < col; ++j)
			{
				pmaze_[i][j].x_ = i;
				pmaze_[i][j].y_ = j;
				pmaze_[i][j].val_ = static_cast<bool>(rand()%2);
			}
		}
	}

	void showMaze()
	{
		cout<<"-------------showMaze begin-----------"<<endl;
		for(int i=0; i<row_; ++i)
		{
			for(int j=0; j<col_; ++j)
			{
				cout<<pmaze_[i][j].val_<<" ";
			}
			cout<<endl;
		}
		cout<<"--------------showMaze end------------"<<endl;
	}

	void searchMazePath()
	{
		int i = 0;
		int j = 0;
		if(pmaze_[0][0].val_ == true)
		{
			return;
		}
		que_.push(pmaze_[0][0]);
		pmaze_[0][0].state_ = true;
		for(;;)
		{
			if(j+1!=col_ && !(pmaze_[i][j+1].val_|pmaze_[i][j+1].state_))
			{
				que_.push(pmaze_[i][j+1]);
				vec_[i*col_+j+1] = {i,j};
				if(i==row_-1 && j == col_-2)
				{
					findPath_ = true;
					break;
				}
				pmaze_[i][j+1].state_ = true;
			}

			if(i+1!=row_ && !(pmaze_[i+1][j].val_|pmaze_[i+1][j].state_))
			{
				que_.push(pmaze_[i+1][j]);
				vec_[(i+1)*col_+j] = {i,j};
				if(i==row_-2 && j==col_-1)
				{
					findPath_ = true;
					break;
				}
				pmaze_[i+1][j].state_ = true;
			}

			if(j!=0 && !(pmaze_[i][j-1].val_|pmaze_[i][j-1].state_))
			{
				que_.push(pmaze_[i][j-1]);
				vec_[i*col_+j-1] = {i,j};
				pmaze_[i][j-1].state_ = true;
			}

			if(i!=0 && !(pmaze_[i-1][j].val_|pmaze_[i-1][j].state_))
			{
				que_.push(pmaze_[i-1][j]);
				vec_[(i-1)*col_+j] = {i,j};
				pmaze_[i-1][j].state_ = true;
			}
			
			que_.pop();
			if(que_.empty())
				break;
			i = que_.front().x_;
			j = que_.front().y_;

		}
	}


//private:
	void showPath()
	{
		if(!path_.empty())
			path_.clear();
		for(int i=0; i<row_; ++i)
		{
			path_.push_back(string());
			for(int j=0; j<col_; ++j)
			{
				path_.back().push_back((char)(pmaze_[i][j].val_+'0'));
				path_.back().push_back(' ');
			}
		}
		if(findPath_)
		{
			int i = row_-1;
			int j = col_-1;
			path_[0][0] = '*';
			while(i!=0 || j!=0)
			{
				path_[i][j*2] = '*';	
				i = vec_[i*col_+j].first;
				j = vec_[i*col_+j].second;
			}
		}
		else 
		{
			cout<<"没有找到迷宫出口"<<endl;
		}

		for(string& str:path_)
		{
			cout<<str<<endl;
		}
	}

private:
	struct Node 
	{
		int x_;
		int y_;
		bool val_;
		bool state_=false;
	};
	
	int row_;
	int col_;
	bool findPath_;
	Node** pmaze_;
	vector<pair<int, int>> vec_;
	queue<Node> que_;
	vector<string> path_;
};

int main()
{
	cout<<"----------main begin------------"<<endl;
	Maze maze;
	maze.initMaze(5, 5);
	maze.showMaze();
	maze.searchMazePath();
	maze.showPath();

	return 0;
}
